RT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <string>

using namespace std;

namespace OpenHash
{
	template<class T>
	class HashFunc
	{
	public:
		size_t operator()(const T& val)
		{
			return val;
		}
	};

	template<>
	class HashFunc<string>
	{
	public:
		size_t operator()(const string& s)
		{
			const char* str = s.c_str();
			unsigned int seed = 131; // 31 131 1313 13131 131313
			unsigned int hash = 0;
			while (*str)
			{
				hash = hash * seed + (*str++);
			}
			return hash;
		}
	};

	template<class V>
	struct HashBucketNode
	{
		HashBucketNode(const V& data)
			: _pNext(nullptr), _data(data)
		{}
		HashBucketNode<V>* _pNext;
		V _data;
	};

	 //本文所实现的哈希桶中key是唯一的
	template<class V, class HF = HashFunc<V>>
	class HashBucket
	{
		typedef HashBucketNode<V> Node;
		typedef Node* PNode;

		typedef HashBucket<V, HF> Self;

	public:
		HashBucket(size_t capacity)
			: _table(capacity)
			, _size(0)
		{}

		~HashBucket()
		{
			Clear();
		}

		// 哈希桶中的元素不能重复
		Node* Insert(const V& data)
		{
			//有数据了发返回nullptr
			if (Find(data) != nullptr)
				return nullptr;

			CheckCapcity();

			size_t hashi = HashFunc(data);
			Node* newnode = new Node(data);
			
			newnode->_pNext = _table[hashi];
			_table[hashi] = newnode;
			_size++;
			return newnode;
		}

		// 删除哈希桶中为data的元素(data不会重复)
		bool Erase(const V& data)
		{
			if (Find(data) == nullptr)
				return false;

			size_t hashi = HashFunc(data);
			Node* cur = Find(data);
			//这样就把要删除的数据都放到了第一个位置
			if (cur != _table[hashi])
			{
				std::swap(cur->data, _table[hashi]._data);
			}
			cur = _table[hashi];
			_table[hashi] = cur->_pNext;
			delete cur;
			_size--;
			return true;
		}

		Node* Find(const V& data)
		{
			size_t hashi = HashFunc(data);
			Node* cur = _table[hashi];
			while (cur != nullptr)
			{
				if (cur->_data == data)
					return cur;
				else
					cur = cur->_pNext;
			}
			return nullptr;
		}

		size_t Size()const
		{
			return _size;
		}

		bool Empty()const
		{
			return 0 == _size;
		}

		void Clear()
		{
			Node* cur = nullptr;
			Node* next = nullptr;
			for (int i = 0; i < _table.size(); i++)
			{
				if (_table[i] != nullptr)
				{
					cur = _table[i];
					next = cur->_pNext;
				}

				while (cur != nullptr)
				{
					delete cur;
					cur = next;
					if(next->_pNext!=nullptr)
					next = next->_pNext;
				}
			}
		}

		size_t BucketCount()const
		{
			return _table.capacity();
		}

		void Swap(Self& ht)
		{
			_table.swap(ht._table);
			swap(_size, ht._size);
		}

	private:
		size_t HashFunc(const V& data)
		{
			return HF()(data) % _table.capacity();
		}

		void CheckCapcity()
		{   //7 hy == 10size
			//负载因子大于70%扩容为二倍
			if (10 * _size >= 7 * _table.capacity())
			{
				HashBucketNode<V> newTb(_table.capacity()*2);
				Node* cur = nullptr;
				for (size_t i = 0; i < _table.capacity(); i++)
				{
					if (_table[i] != nullptr)
					{
						cur = _table[i];
						while (cur != nullptr)
						{
							newTb.Insert(cur->_data);
							cur = cur->_pNext;
						}
					}
				}
				Swap(newTb);
			}
		}
	private:
		vector<Node*> _table;
		size_t _size;      // 哈希表中有效元素的个数
	};
}

int main()
{
	//OpenHash::HashBucket<string> hb(5);
	//hb.Insert("1");
	//hb.Insert("4");
	//hb.Insert("7");
	//hb.Insert("6");
	//hb.Insert("12");
	//hb.Insert("13");
	//hb.Insert("12");

	//OpenHash::HashBucket<int> hb(5);
	//hb.Insert(8);
	//hb.Insert(2);
	//hb.Insert(3);
	//hb.Insert(9);
	//hb.Insert(7);
	return 0;
}
